1. Field of the Invention
The present invention relates to a circuit arranged to perform a cyclic redundancy check (CRC) on a received data stream. The circuit may additionally be used to perform other forms of coding on selected data.
2. Description of the Related Art
Error coding is often added to data when there is a possibility that the data may be corrupted or otherwise interfered with during transmission. Simple error coding may include simply adding a parity bit which indicates to the receiver that the data received is not identical with the data transmitted. However, such simple schemes do not protect for cases where more than a single bit is at fault. This can pose problems when, in reality, a burst error may corrupt several bits in a message.
Cyclic Redundancy Checking (CRC) is one form of error checking employed in a wide variety of data traffic systems. CRC uses a system of polynomial division to code a given string of data.
For example, assume the message to be transmitted is a multi-bit message, M(D).DN. This message is divided, using modulo-2 arithmetic, by a so-called generator polynomial, G(D). This division yields a division polynomial, Y(D), and a remainder polynomial R(D).
                                                        M              ⁡                              (                D                )                                      .                          D              N                                            G            ⁡                          (              D              )                                      =                              Y            ⁡                          (              D              )                                +                      R            ⁡                          (              D              )                                                          (        1        )            
The long division process (normal, or modulo-2 for polynomials) yields Y(D) and R(D) as two separate outputs. In practice, only the remainder, R(D), is of interest, and Y(D) is discarded. The message, M(D) is then normally appended by N zero digits, or simply shifted left N positions, where N is the order of the generator polynomial, G(D). The data that is transmitted is therefore: M(D).DN+R(D).
The data may be transmitted over any one of a number of different interfaces. During the course of the transmission, an error E(D) may occur. The error may affect one or more bits of the message, which means that the receiver will receive M(D).DN+R(D) +E(D).
In order to verify the authenticity of the received data, the receiver divides the received data by the same generator polynomial, G(D).
                                                                        M                ⁡                                  (                  D                  )                                            .                              D                N                                      +                          R              ⁡                              (                D                )                                      +                          E              ⁡                              (                D                )                                                          G            ⁡                          (              D              )                                      =                                                            M                ⁡                                  (                  D                  )                                            .                              D                N                                                    G              ⁡                              (                D                )                                              +                                    R              ⁡                              (                D                )                                                    G              ⁡                              (                D                )                                              +                                    E              ⁡                              (                D                )                                                    G              ⁡                              (                D                )                                                                        (        2        )            
The first term in the result of equation (2) yields Y(D) and R(D) as before. The term R(D)/G(D) yields just the remainder R(D). The term E(D)/G(D) yields e(D) and r(D) which represent the errors introduced by E(D).
The result of the division by the receiver, may therefore be written as:(Y(D)+e(D))+R(D)+R(D)+r(D)  (3)
Y(D) is not significant, as before, and may simply he discarded. The same is true for e(D), which is the result of E(D) divided by G(D). In practice, Y(D) and e(D) are combined and cannot be separated.
Accordingly, if no error E(D) has occurred during transmission, then r(D) is zero. If an error E(D) has occurred, then r(D) will have a non-zero value. In such a case, the receiver may choose to ignore the received data, flag it as erroneous and/or request a re-transmission.
As an example of this procedure, consider a binary stream of 192 bits: {1011 . . . 011}. Representing this as a polynomial already appended (or shifted) with eights ‘0’s to take into account the order of the generator, G(D):1.D199+0.D198+1.D197+1.D196+ . . . +0.D10+1.D9+1.D8+0.D7+0.D6+0.D5+ . . . +0.D1+0.D+0.D0  (4)
The generator polynomial, G(D), of order N=8, in this case is:D8+D7+D4+D3+D1+D0  (5)
In hardware, the modulo-2 division may be implemented as shown in FIG. 1. FIG. 1 shows a circuit 20, including a string of sequentially connected registers 22. An XOR gate 24 is interposed between adjacent shift registers at the appropriate positions to realize the algorithm of equation (5).
The data to be encoded is shifted into the coder 20 as shown in FIG. 1. After all the data bits have been shifted into the coder, a sequence of zero bits are shifted in. The sequence consists of as many zero bits as there are bits in the coder. In the present case, the sequence of zero bits is 8 bits long.
After the sequence of zero bits has been loaded into the coder, the coder 20 contains the remainder R(D) of the coding division process.
The same coder circuit may be used for encoding and decoding. For encoding, the procedure is as described above. For decoding received data, the message data is first shifted into the coder 20, followed by the received remainder, R(D). If the coder 20 stores a zero value after the remainder has been shifted in, this indicates that the message and remainder sequence were received without error. A non-zero result indicates that either the message or remainder contains an error.
The CRC function can also be implemented in software. The following code demonstrates a prior art realization.
for (i=0; i<data_len; i++){C=M[i];//Get the next input data bitC= C {circumflex over ( )}CRC[0];//XOR data bit with LSB of CRC registerif (CRC[0]==1){for (j=0; j<CRC_len; j++){CRC[j] = CRC[j] {circumflex over ( )}CRC_poly[j];//XOR CRC bits with generator polynomial bits}}//Shift CRC register bits right by one positionfor (j=0; j<CRC_len - 1; j++){CRC[j] = CRC[j+1];}CRC[CRC_len - 1] = C//C becomes the new MSB of CRC register}
From the code above, it is evident that using a normal DSP (Digital Signal Processor) or MCU (Microprocessor Unit), a total of 3–5 instruction cycles would be required each time the LSB of the CRC register is checked for a ‘1’, performing the XOR and shift operations. The speed of this operation is further reduced when the length of the CRC register is higher than the data width of the processor or DSP accumulators, which are normally 8, 16, 24 or 32 bits. In such cases, two or more sets of XOR and shift are required.